package DataStructure;

/**
 * @time: 2021/3/29/029 20:13
 * @author: Zhurunhe
 */
public class StackDemo {
    public static void main(String[] args) {
        String expression = "10+2+6*3/2-20";
        CIntStack numStack = new CIntStack(100);
        CIntStack operStack = new CIntStack(100);
        boolean isRight = true;//判断表达式是否正确
        int index = 0;//扫描指针
        int num1 = 0;
        int num2 = 0;
        int res = 0;
        int oper = 0;
        String keepNum = "";//用于拼接多位数字
        char ch = ' ';//扫描到的char保存到ch中
        while (true) {
            ch = expression.substring(index, index + 1).charAt(0);//循环取内容
            if (operStack.isOper(ch)) {
                if (operStack.isEmpty()) {
                    operStack.push(ch);
                } else {
                    if (ch == '/' && expression.substring(index + 1, index + 2).charAt(0) == '0') {
                        System.out.println("除数不能为0");
                        isRight = false;
                        break;
                    }
                    //如果符号栈不为空，则进行比较
                    //ch的优先级小于<=栈中符号的优先级，则pop出两个数和一个符号进行运算，
                    // 然后将运算结果放入数字栈中，最后再将ch放入符号栈中
                    if (operStack.priotity(ch) <= operStack.priotity(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        //如果ch的优先级小于>栈中符号的优先级，则直接入栈
                        operStack.push(ch);

                    }
                }

            } else {
                //数值栈则直接入栈 注意数字1对应的ASCII值 为49 需要减1

                keepNum += ch;//拼接数字
                //先判断是否扫描到表达式的尾端 如果是直接插入
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //如果没到尾端 则需要继续扫描下一位 判断是否为数字，是数字就继续扫描 如果是运算符则入栈
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";//让拼接字符重新为空 避免拼接到下一个字符中
                    }
                }
            }
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        //扫描结束后 顺序pop出oper和num 进行运算 然后将结果重新放入到numStack中
        //最后numStack存储的数就是表达式的结果
        if (isRight) {
            while (true) {
                if (operStack.isEmpty()) {
                    break;
                }
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = operStack.pop();
                res = numStack.cal(num1, num2, oper);
                numStack.push(res);

            }
            System.out.println(expression + "=" + numStack.pop());
        }

    }

}

class CIntStack {
    private int[] intstack;
    private int maxsize;
    private int top = -1;

    public CIntStack(int maxsize) {
        this.maxsize = maxsize;
        intstack = new int[maxsize];
    }

    public boolean isFull() {
        return top == maxsize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(int values) {
        if (isFull()) {
            System.out.println("---------栈已满");
            return;
        }
        top++;
        intstack[top] = values;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("---------栈空");
        }
        int valuse = intstack[top];
        top--;
        return valuse;
    }

    //符号的优先级
    public int priotity(int oper) {
        if ('(' == oper || ')' == oper) {
            return 2;
        } else if ('*' == oper || '/' == oper) {
            return 1;
        } else if ('+' == oper || '-' == oper) {
            return 0;
        } else {
            return -1;
        }
    }

    //判断是否为操作符
    public boolean isOper(int oper) {
        return oper == '/' || oper == '*' || oper == '-' || oper == '+' || oper == '(' || oper == ')';
    }

    //返回栈顶的值 但不出栈
    public int peek() {
        return intstack[top];
    }

    //计算
    public int cal(int num1, int num2, int oper) {
        int res = 0;//结果
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;

            default:
                break;
        }
        return res;
    }

    public void show() {
        if (isEmpty()) {
            throw new RuntimeException("---------栈空");
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(intstack[i]);
        }
    }

}